package com.czk.graph.grapnpractice;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @Author:ChenZhangKun
 * @Date: 2020/8/6 22:52
 */
public class GraphDemo {

}
class Graph{
    /**
     * 顶点的集合
     */
    private List<String> vertexList;
    /**
     * 边数
     */
    private int edgeNum;
    /**
     * 邻接矩阵
     */
    private int[][] edges;
    /**
     * 是否被访问
     */
    private boolean[] isVisited;
    /**
     * 构造方法
     */
    public Graph(int n){
        edges=new int[n][n];
        isVisited=new boolean[n];
        vertexList=new ArrayList<>();
        edgeNum=0;
    }

    /**
     *
     * @param v1 顶点一的索引
     * @param v2 顶点二的索引
     * @param weight 权值
     */
    public void addEdge(int v1,int v2,int weight){
        edges[v1][v2]=weight;
        edges[v2][v1]=weight;
        edgeNum++;
    }
    public void add(String vertex){
        vertexList.add(vertex);
    }
    /**
     * 获取一个顶点的第一条边
     * @param v 顶点索引
     * @return 相邻节点索引
     */
    public int getFirstNeighbor(int v){
        for (int i = 0; i < vertexList.size(); i++) {
            if (edges[v][i]>0){
                // 找到边
                return i;
            }
        }
        // 没有找到边
        return -1;
    }

    /**
     * 获取第二个邻接顶点
     * @param v 行数
     * @param v1 当前第几列
     * @return 索引
     */
    public int getNextNeighbor(int v,int v1){
        for (int i = v1+1; i < vertexList.size(); i++) {
            if (edges[v][i]>1){
                return i;
            }
        }
        return -1;
    }

    /**
     * 图的深度优先遍历
     * @param isVisited 是否被访问
     * @param i 开始的索引
     */
    public void dfs(boolean[] isVisited,int i){
        System.out.print(vertexList.get(i)+"->");
        // 将当前顶点置为已访问
        isVisited[i]=true;
        // 拿到第一个邻接节点
        int firstNeighbor = this.getFirstNeighbor(i);
        while (firstNeighbor!=-1){
            // 有没有被访问
            if (!isVisited[firstNeighbor]){
                // 递归
                dfs(isVisited,firstNeighbor);
            }
            // 寻找当前行的下个邻接节点
            firstNeighbor=this.getNextNeighbor(i,firstNeighbor);
        }
    }

    /**
     * 遍历所有行
     */
    public void dfs(){
        for (int i = 0; i < vertexList.size(); i++) {
            if (!isVisited[i]){
                dfs(isVisited,i);
            }
        }
    }

    public static void main(String[] args) {
        // 测试数组
        // 节点的个数
        int n=5;
        String[] vertexValue={"A","B","C","D","E"};
        // 创图对象
        Graph graph=new Graph(n);
        for (String s : vertexValue) {
            graph.add(s);
        }
        // 添加边A->B
        graph.addEdge(0,1,1);
        graph.addEdge(0,2,1);
        graph.addEdge(1,2,1);
        graph.addEdge(1,3,1);
        graph.addEdge(1,4,1);
        // dfs
        graph.showGraph();
        graph.dfs();
    }

    /**
     *
     */
    public void showGraph() {
        // 遍历数组
        for (int[] edge : edges) {
            System.out.println(Arrays.toString(edge));
        }
    }
}
